package com.maishi.programmer.jainzhioffer;


/**
 * Created by brossdong on 2018/3/27.
 * 合并两个排序链表
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
 */
public class TestProblem25 {

    /**
     * 构造一个单链表
     */
    public class ListNode {
        int val;
        ListNode next = null;
        ListNode (int val) {
            this.val = val;
        }
    }

    public ListNode Merge(ListNode list1,ListNode list2) {
        //链表1为空 链表2不为空
        if (list1 == null) return list2;
        //链表1不为空 链表1为空
        if (list2 == null) return list1;
        //都为空
        if (list1 == null && list2 == null) return null;

        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next,list2);
            return list1;
        } else {
            list2.next = Merge(list1,list2.next);
            return list2;
        }

    }

}
